import java.util.*;

public class SetManipulator {
	private ArrayList<String> derivable;

	public SetManipulator() {
		derivable = new ArrayList<String>();
	}

	public ArrayList<ArrayList<String>> computeMaxSets2(ArrayList<String> r,
			ArrayList<String> r_s, ArrayList<FuncDep> fd) {
		// Initialize maxSets
		ArrayList<ArrayList<String>> maxSets = new ArrayList<ArrayList<String>>();
		for (int i = 0; i < r.size(); i++) {
			ArrayList<String> temp = new ArrayList<String>();
			for (int j = 0; j < r.size(); j++) {
				if (j != i) {
					temp.add(r.get(j));
				}
			}
			maxSets.add(temp);
		}

		// Initialize theta
		ArrayList<FuncDep> theta = new ArrayList<FuncDep>();

		for (int i = 0; i < fd.size(); i++) {
			// Increse theta
			theta.add(fd.get(i));

			// Initialize nmax
			ArrayList<ArrayList<String>> nmax = new ArrayList<ArrayList<String>>();
			for (int p = 0; p < r.size(); p++) {
				nmax.add(maxSets.get(p));

				for (int w = 0; w < nmax.get(p).size(); w++) {
					if (!mtest(nmax.get(p).get(w), r.get(p), r, r_s, theta)) {
						// Remove W from nmax
						nmax.get(p).remove(w--);

						// Temporarily skip the rest
					}
				}
			}

			maxSets.clear();
			for (int j = 0; j < nmax.size(); j++) {
				maxSets.add((nmax.get(j)));
			}
		}

		return maxSets;
	}

	private boolean mtest(String w, String c, ArrayList<String> r,
			ArrayList<String> r_s, ArrayList<FuncDep> theta) {
		ArrayList<String> right = new ArrayList<String>();
		right.add(c);

		if (back_trace_derivable(w, right, r, r_s, theta) > 0) {
			return false;
		} else {
			return true;
		}
	}

	private int back_trace_derivable(String w, ArrayList<String> right,
			ArrayList<String> r, ArrayList<String> r_s, ArrayList<FuncDep> theta) {
		// Base case for the exact checking
		for (int i = 0; i < theta.size(); i++) {
			FuncDep fd = theta.get(i);
			if (belongs(right, fd.getTo())) {
				if (fd.getFrom().size() == 1 && fd.getFrom().get(0).equals(w)) {
					return 1;
				}
			}
		}

		// Recursive cases
		int result = 0;
		for (int i = 0; i < theta.size(); i++) {
			FuncDep fd = theta.get(i);
			boolean no_null = true;

			// Checking for null, if there is the recursion stop this branch
			for (int j = 0; j < fd.getFrom().size(); j++) {
				if (!r_s.contains(fd.getFrom().get(j))) {
					no_null = false;
				}
			}

			// Recursive call
			if (belongs(right, fd.getTo()) && no_null) {
				result += back_trace_derivable(w, fd.getFrom(), r, r_s, theta);
			}
		}

		return result;
	}

	public ArrayList<ArrayList<String>> computeMaxSets(ArrayList<String> r,
			ArrayList<String> r_s, ArrayList<FuncDep> fd) {
		ArrayList<ArrayList<String>> maxSets = new ArrayList<ArrayList<String>>();

		for (int i = 0; i < r.size(); i++) {
			ArrayList<String> maxSet = new ArrayList<String>();

			// Finding the derivable set
			this.derivable.clear();
			// findDerivables(r.get(i), r_s, fd);

			// Finding the max set
			for (int j = 0; j < r.size(); j++) {
				if (j != i && !derivable.contains(r.get(j))) {
					maxSet.add(r.get(j));
				}
			}

			maxSets.add(maxSet);
		}

		return maxSets;
	}

	// private void findDerivables(String att, ArrayList<String> r_s,
	// ArrayList<FuncDep> fd) {
	// for (int i = 0; i < fd.size(); i++) {
	// String from = fd.get(i).getFrom();
	// String to = fd.get(i).getTo();
	//
	// if (to.equals(att) && !this.derivable.contains(from)) {
	// this.derivable.add(from);
	// // fd.remove(i--);
	// if (r_s.contains(from)) {
	// findDerivables(from, r_s, fd);
	// }
	// }
	// }
	// }

	public ArrayList<String> union2(ArrayList<String> z, ArrayList<String> rs_X) {
		ArrayList<String> union = new ArrayList<String>();

		for (int i = 0; i < z.size(); i++) {
			if (!union.contains(z.get(i))) {
				union.add(z.get(i));
			}
		}

		for (int i = 0; i < rs_X.size(); i++) {
			if (!union.contains(rs_X.get(i))) {
				union.add(rs_X.get(i));
			}
		}

		return union;
	}

	public ArrayList<String> subtract(ArrayList<String> big,
			ArrayList<String> small) {
		ArrayList<String> result = new ArrayList<String>();

		for (int i = 0; i < big.size(); i++) {
			if (!small.contains(big.get(i))) {
				result.add(big.get(i));
			}
		}

		return result;
	}

	public ArrayList<String> union3(ArrayList<String> x, ArrayList<String> z,
			ArrayList<String> r_s) {
		ArrayList<String> union = new ArrayList<String>();

		for (int i = 0; i < x.size(); i++) {
			if (!union.contains(x.get(i))) {
				union.add(x.get(i));
			}
		}

		for (int i = 0; i < z.size(); i++) {
			if (!union.contains(z.get(i))) {
				union.add(z.get(i));
			}
		}

		for (int i = 0; i < r_s.size(); i++) {
			if (!union.contains(r_s.get(i))) {
				union.add(r_s.get(i));
			}
		}

		return union;
	}

	public boolean belongs(ArrayList<String> small, ArrayList<String> big) {
		for (int i = 0; i < small.size(); i++) {
			if (!big.contains(small.get(i))) {
				return false;
			}
		}
		return true;
	}
}
